//! @file   lc_linked_list.h
//! @brief  
//! @author Sayan Chaliha
//! @date   September, 2011
//!
//! 
#ifndef _LC_LINKED_LIST_H
#define _LC_LINKED_LIST_H

#include "libcyan_internal.h"
#include "lc_types.h"
#include "lc_object.h"
#include "lc_iterator.h"
#include "lc_exception.h"

namespace cyan {
  namespace internal {
    struct CYAN_HIDDEN ListNodeBase {
      ListNodeBase* next;
      ListNodeBase* previous;

      static void swap(ListNodeBase& node1, ListNodeBase& node2) throw() {
        ListNodeBase* temp = node1.next;
        node1.next = node2.next;
        node2.next = temp;

        temp = node1.previous;
        node1.previous = node2.previous;
        node2.previous = temp;
      }

      void transfer(ListNodeBase* const firstNode,
          ListNodeBase* const lastNode) throw() {
        firstNode->previous->next = lastNode->next;
        lastNode->next->previous = firstNode->previous;

        this->previous->next = firstNode;
        firstNode->previous = this->previous;

        this->previous = lastNode;
        lastNode->next = this;
      }

      void reverse() throw() {
        ListNodeBase* temp = this->next;
        this->next = this->previous;
        this->previous = temp;
      }

      void hook(ListNodeBase* const position) throw() {
        this->previous = position->previous;
        this->next = position;

        position->previous->next = this;
        position->previous = this;
      }

      void unhook() throw() {
        this->previous->next = this->next;
        this->next->previous = this->previous;
      }
    };

    template <typename T>
    struct CYAN_HIDDEN ListNode : public ListNodeBase {
      T data;
    };

    template <typename T>
    struct CYAN_API ListIterator {
      typedef T                                   ValueType;
      typedef cyan::PtrDiff                       DifferenceType;
      typedef cyan::BidirectionalIteratorTag      IteratorCategory;
      typedef T*                                  Pointer;
      typedef T&                                  Reference;

      ListIterator() : node() {
      }

      ListIterator(ListNodeBase* n) : node(n) {
      }

      Reference operator *() const {
        return (static_cast<ListNode<T>*>(this->node))->data;
      }

      Pointer operator ->() const {
        return &((static_cast<ListNode<T>*>(this->node))->data);
      }

      ListIterator& operator ++() {
        this->node = this->node->next;
        return *this;
      }

      ListIterator& operator ++(cyan::Int) {
        ListIterator temp = *this;
        this->node = this->node->next;
        return temp;
      }

      ListIterator& operator --() {
        this->node = this->node->next;
        return *this;
      }

      ListIterator& operator --(cyan::Int) {
        ListIterator temp = *this;
        this->node = this->node->next;
        return temp;
      }

      Bool operator ==(const ListIterator& value) const {
        return this->node == value.node;
      }

      Bool operator !=(const ListIterator& value) const {
        return this->node != value.node;
      }

      ListNodeBase* node;
    };

    template <typename T>
    struct CYAN_API ConstListIterator {
      typedef T                                   ValueType;
      typedef cyan::PtrDiff                       DifferenceType;
      typedef cyan::BidirectionalIteratorTag      IteratorCategory;
      typedef const T*                            Pointer;
      typedef const T&                            Reference;
      typedef ListIterator<T>                     Iterator;

      ConstListIterator() : node() {
      }

      ConstListIterator(const ListNodeBase* n) : node(n) {
      }

      ConstListIterator(const Iterator& i) : node(i.node) {
      }

      Reference operator *() const {
        return (static_cast<const ListNode<T>*>(this->node))->data;
      }

      Pointer operator ->() const {
        return &((static_cast<const ListNode<T>*>(this->node))->data);
      }

      ConstListIterator& operator ++() {
        this->node = this->node->next;
        return *this;
      }

      ConstListIterator& operator ++(cyan::Int) {
        ConstListIterator temp = *this;
        this->node = this->node->next;
        return temp;
      }

      ConstListIterator& operator --() {
        this->node = this->node->previous;
        return *this;
      }

      ConstListIterator& operator --(cyan::Int) {
        ConstListIterator temp = *this;
        this->node = this->node->previous;
        return temp;
      }

      Bool operator ==(const ConstListIterator& value) const {
        return this->node == value.node;
      }

      Bool operator !=(const ConstListIterator& value) const {
        return this->node != value.node;
      }

      const ListNodeBase* node;
    };

    template <typename T>
    inline cyan::Bool
    operator ==(const ListIterator<T>& lhs, const ConstListIterator<T>& rhs) {
      return lhs.node == rhs.node;
    }

    template <typename T>
    inline cyan::Bool
    operator !=(const ListIterator<T>& lhs, const ConstListIterator<T>& rhs) {
      return lhs.node != rhs.node;
    }

    template <typename T>
    class CYAN_HIDDEN ListBase : public Object {
    public:
      ListBase() {
        this->initialize();
      }

      virtual ~ListBase() {
        this->clear();
      }

      void initialize() {
        this->node_.next = &this->node_;
        this->node_.previous = &this->node_;
      }

      void clear();

    protected:
      static ListNode<T>* getNode() {
        return reinterpret_cast<ListNode<T>*>(::malloc(sizeof (ListNode<T>)));
      }

      static void putNode(ListNode<T>* node) {
        free(node);
      }

      ListNodeBase node_;
    };
  }

  template <typename T>
  class CYAN_API LinkedList : protected internal::ListBase<T> {
  public:
    typedef T                                   ValueType;
    typedef T*                                  Pointer;
    typedef const T*                            ConstPointer;
    typedef T&                                  Reference;
    typedef const T&                            ConstReference;
    typedef internal::ListIterator<T>           Iterator;
    typedef internal::ConstListIterator<T>      ConstIterator;
    typedef Size                                SizeType;
    typedef PtrDiff                             DifferenceType;

    typedef internal::ListBase<T>               Base;
    typedef internal::ListNode<T>               Node;

    LinkedList() : Base() {
    }

    LinkedList(const LinkedList& otherList) : Base() {
      this->insert(this->begin(), otherList.begin(), otherList.end());
    }

    template <typename I>
    LinkedList(I first, I last) : Base() {
      this->insert(this->begin(), first, last);
    }

    Iterator begin() {
      return Iterator(this->node_.next);
    }

    ConstIterator begin() const {
      return ConstIterator(this->node_.next);
    }

    Iterator end() {
      return Iterator(&this->node_);
    }

    ConstIterator end() const {
      return ConstIterator(&this->node_);
    }

    Bool isEmpty() const {
      return this->node_.next == &this->node_;
    }

    SizeType size() const {
      return distance(this->begin(), this->end());
    }

    SizeType length() const {
      return distance(this->begin(), this->end());
    }

    Iterator erase(Iterator first, Iterator last) {
      while (first != last)
        first = this->erase(first);
      return last;
    }

    SizeType maximumSize() const {
      return (SizeType(-1) / (sizeof (ValueType) * 1024 * 1024));
    }

    Reference front() {
      return *this->begin();
    }

    ConstReference front() const {
      return *this->begin();
    }

    Reference back() {
      return *(--this->end());
    }

    ConstReference back() const {
      return *(--this->end());
    }

    LinkedList& pushFront(ConstReference value) {
      this->insert(this->begin(), value);
      return *this;
    }

    LinkedList& popFront() {
      this->eraseHelper(this->begin());
      return *this;
    }

    LinkedList& pushBack(ConstReference value) {
      this->insert(this->end(), value);
      return *this;
    }

    LinkedList& popBack() {
      this->eraseHelper(this->end());
      return *this;
    }

    void clear() {
      Base::clear();
      Base::initialize();
    }

    template <typename I>
    void insert(Iterator position, I first, I last) {
      typedef typename IsIntegral<I>::Type Integral;
      this->insertDispatch(position, first, last, Integral());
    }

    void insert(Iterator position, SizeType length, ConstReference value) {
      this->fillInsert(position, length, value);
    }

    void splice(Iterator position, Iterator i) {
      Iterator j = i;
      if (position == i || position == j)
        return;
      this->transfer(position, i, j);
    }

    Iterator insert(Iterator, ConstReference);
    Iterator erase(Iterator);
    void remove(ConstReference);
    void splice(Iterator, Iterator, Iterator);
    void splice(Iterator, LinkedList&);
    void unique();

    template <typename BinaryPredicate>
    void unique(BinaryPredicate);

    template <typename UnaryPredicate>
    void removeIf(UnaryPredicate);

    LinkedList& operator =(const LinkedList&);

  protected:
    using Base::node_;
    using Base::getNode;
    using Base::putNode;

    static Node* createNode(const ValueType& value) {
      Node* node = LinkedList::getNode();

      if (!node)
        Exception::throwException
            (OutOfMemoryException(TEXT("LinkedList::createNode")));

      try {
        node->data = *new (static_cast<void*>(&node->data))
        ValueType(value);
      } catch (...) {
        LinkedList::putNode(node);
#ifdef LC_EXCEPTIONS
        throw;
#endif /* LC_EXCEPTIONS */
      }
      return node;
    }

    static Node* createNode() {
      Node* node = LinkedList::getNode();

      if (!node)
        Exception::throwException
            (OutOfMemoryException(TEXT("LinkedList::createNode")));

      try {
        node->data = *new (static_cast<void*>(&node->data))
        ValueType(ValueType());
      } catch (...) {
        LinkedList::putNode(node);
#ifdef LC_EXCEPTIONS
        throw;
#endif /* LC_EXCEPTIONS */
      }
      return node;
    }

    void transfer(Iterator position, Iterator first, Iterator last) {
      position.node->transfer(first.node, last.node);
    }

    void eraseHelper(Iterator position) {
      position.node->unhook();
      Node* node = static_cast<Node*>(position.node);
      node->data.~T();
      LinkedList::putNode(node);
    }

    void insertHelper(Iterator position, ConstReference value) {
      Node* temp = LinkedList::createNode(value);
      temp->hook(position.node);
    }

    template <typename I>
    void insertDispatch(Iterator position, I first, I last, FalseType) {
      for (; first != last; ++first)
        this->insertHelper(position, *first);
    }

    void fillInsert(Iterator position, SizeType length, ConstReference value) {
      for (; length > 0; --length)
        this->insertHelper(position, value);
    }

    template <typename I>
    void insertDispatch(Iterator position, I first, I last, TrueType) {
      this->fillInsert(position, static_cast<SizeType> (first),
          static_cast<ValueType>(last));
    }
  };
}

#include "lc_linked_list_impl.h"

#endif /* _LC_LINKED_LIST_H */
